1. Field of the Invention
The present invention relates generally to the field of computational placement of elements, and more specifically to efficiently placing or locating photographs or graphic images on a page.
2. Description of the Related Art
Computer software is currently available for a user to collect and display graphical images in a visually pleasing format. Such computer software develops what have been called photo albums, comprising a series of pages having images selected by the user and arranged in various manners. A photo album page, as the term is used herein, refers to multiple graphical images or pictures positioned on a page of fixed size. Graphical images or pictures as used herein refer to a software depiction of virtually anything, including text, such that the graphical image or picture can be considered to have a rectangular boundary. Examples of graphical files include .gif, .tiff and .jpeg graphical representations, but can include virtually any image having a boundary. For example, an oval shape block of text may be considered a graphical image or picture having rectangular borders touching the top, bottom, left, and right side of the oval shape block, including an optional border.
In deciding how and where to place graphical images on a photo album page, software must address various environment specific issues. For example, the number of pictures on the page, the size of the pictures relative to each other, spatial distribution of pictures, available empty space, and the existence of captions all factor into the placement of the selected graphical images on the photo album page.
In previous software systems for arranging graphical images, arrangement frequently occurred “by hand.” In this process, the user opened a blank page document and imported digital graphical images. Software generated a “layout” on the photo album page by enabling the user to move images around the page, and possibly allowing resizing, so as to achieve a pleasing picture layout. The process of moving and resizing photos by hand can be tedious and time consuming. In response, developers have created automated software packages intended to at least partially automate the layout process.
Certain software packages automate the layout process by positioning images in rows and columns. By forcing images to fall into separate regions all of the same size and shape, layouts produced with this type of software package do not account for image aspect ratios, and graphical images may appear distorted when placed in the layout. This type of solution can lead to unused empty space on the page, which is visually unattractive and wastes available space.
Other software packages provide templates, where images are manually inserted into fixed template openings, or “holes.” Templates can be attractive and can make efficient use of space, but available templates are often unusable due to the failure of aspect ratios for template holes to correlate with aspect ratios of images. While the image can be cropped to provide an acceptable appearance and aspect ratio within a particular template hole, cropping is generally unsatisfactory, as it requires discarding part of the image. Also, while the image can be reduced in order to appear complete and uncropped through the template hole, such size reduction can be unsatisfactory because the image appears smaller and is therefore more difficult to see. Some software packages allow the user to create new templates, but the template creation process is typically tantamount to manual layout, and hence tedious and time consuming.
Certain generally available software packages have specific layout design issues. Kodak Memory Albums (“KMA”) exhibits tendencies that appear to automatically generate album page layouts without using templates. KMA does, however, leave empty space that could be occupied by simply enlarging a nearby image. Also, if the user does not like the layout generated, he or she is afforded only one or two alternative layouts. A universe of less than four layouts is generally very limiting.
Canon PhotoRecord Gold (“CPG”) is another software package that provides automatic photo album page layout. In one mode, CPG appears to employ a method for creating templates that accommodate the desired number of images. However, image sizes appear to be ignored in this mode, which can result in image overlap. The image overlap is irregular and often excessive and thus generally unattractive. Alternately, the CPG user can move one image on the page, while the software shifts the other images around the page to accommodate the image being moved. Control of image position shifting appears to be haphazard and in some cases results in images being completely obscured.
Another product called FotoFusion (“FF”) from LumaPix generates single-page collages of photos. FF has an autocollage feature that takes a list of input images and generates a layout of all the images on a single page, and provides an ability to generate various alternative layouts. In the layouts generated by the autocollage feature, little or no white space exists between the photos, and the photos fit together like bricks in a wall. However, the photos in the layout are cropped, and parts of the photos are discarded, which is undesirable.
None of the presently available software designs allows the user to specify relative image size for multiple images while simultaneously retaining the entirety of the images presented. Specification of relative image size can be desirable when, for example, the user wants one image to be significantly larger than all the others on the page. Further, no presently available software design completely eliminates empty, unused space within the rectangular region occupied by images on the page, while simultaneously retaining the entirety of the images presented. This rectangular region may be described as the “convex hull” staked out by the images.
Certain floor planning or layout tree structures have been employed in different contexts. For example, others have used layout tree structures for VLSI circuit layout and for general document layout. In VLSI circuit layout, however, the circuits can be fixed in size, but do not typically have fixed aspect ratios. Circuits can thus be altered independently in x and y dimensions without regard to maintaining a ratio between x and y. Floor planning solutions tend to materially differ from image placement designs due to the aspect ratio maintenance requirements frequently associated with image placement designs. In general document layout, as opposed to image layout, aspect ratios are also considered variable.
It would therefore be desirable to offer a software solution to placing graphical images on a page efficiently with a minimal amount of empty space and a maximum variety of layout designs, while at the same time refraining from cropping the images received, and minimizing drawbacks associated with previous graphical placement software.